package com.heima.leetcode.practice;

import java.util.*;
import java.util.function.Consumer;

/**
 * @description: leetcode 114 二叉树展开为链表
 * @author 勾新杰
 * @version 1.0
 * @date 2025/1/13 23:26
 */
public class E114 {

    private TreeNode prev = null; // 遍历过程中，记录上一个节点

    /**
     * <h3>方法一：借助prev先序遍历，空间复杂度：O(H)</h3>
     * @param root 二叉树根节点
     */
    public void flatten1(TreeNode root) {
        preorder(root);
    }

    /**
     * 先序遍历
     * @param root 二叉树根节点
     */
    private void preorder(TreeNode root) {
        if (root == null) return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (prev != null){
            prev.left = null;
            prev.right = root;
        }
        prev = root;
        preorder(left);
        preorder(right);
    }

    /**
     * <h3>方法二：原地动，空间复杂度：O(1)</h3>
     * @param root 二叉树根节点
     */
    public void flatten2(TreeNode root) {
        // 1. 按照先序遍历处理根节点
        if (root == null) return;
        // 2. 按照先序遍历处理左子树
        flatten2(root.left);
        // 3. 按照先序遍历处理右子树
        flatten2(root.right);
        // 4. 重构当前树
        // 4.0 判断根节点是否有左子树，没有左子树，直接返回
        if (root.left == null) return;
        // 4.1 将右子树接到左子树（如果有）的最右边
        TreeNode curr = root.left;
        while (curr.right != null)
            curr = curr.right;
        curr.right = root.right;
        // 4.2 将左子树接到根节点的右子树
        root.right = root.left;
        // 4.3 将左子树置为null
        root.left = null;
    }
}
